This invention relates to data interleavers and to methods of interleaving data symbols, and is particularly concerned with a so-called channel interleaver for interleaving data symbols in a communications system.
It is well known to perform interleaving of data in a communications system using forward error correction (FEC) in order, on deinterleaving, to distribute errors to facilitate their correction. Typically, such interleaving uses a block interleaver to interleave blocks of data. So-called turbo coding (parallel concatenated convolutional coding) uses an interleaver between inputs to two convolutional coders which produce respective parity bits from the input data before and after interleaving. With increasing attention being given to the use of turbo coding, particularly in wireless communications systems, attention has also been given to the form of the interleaver.
So-called 3rd generation CDMA (code division multiple access) wireless communications systems are also being developed which require a channel or inter-frame interleaver which operates to interleave or permute data in blocks corresponding to the radio frame duration, typically 10 ms. For example, a multi-stage block interleaver (MIL) has been proposed for channel (inter-frame) interleaving and for intra-frame interleaving.
However, in such systems the channel interleaver either precedes or follows a rate matching function which serves to match various data rates to the radio frame rate, and which typically involves puncturing (omission) of data symbols. It is necessary to avoid consecutive puncture of adjacent data symbols of coded blocks of data symbols, but the multi-stage interleaver suffers from a problem in this respect. A so-called potential punturing grid (PPG) concept has been proposed to correct this problem, but the choice of an appropriate PPG depends on variables such as the frame size, number of frames, puncturing rate, and puncturing position.
Accordingly, it would be desirable to provide an interleaver which maximizes the distances by which adjacent punctured data symbols are separated, for arbitrary puncturing rates and puncturing positions, without any PPG.
An object of this invention is to provide an improved data interleaver and method of interleaving data symbols.
According to one aspect, this invention provides a method of interleaving data symbols comprising permuting rows and columns of a matrix of Nr rows and Nc columns, in which data symbols to be interleaved are represented row by row, in accordance with:
where Ir(k) represents a data symbol with a row index k, k is an integer from 1 to Nr, xcex1r is an integer, fc(l) is a non-zero function of a column index l, l is an integer from 1 to Nc, Ic(l) represents a data symbol with the column index l, xcex1c is an integer, fr(k) is zero or a function of the row index k, and modnr and modnc represent modulo-Nr and modulo-Nc arithmetic respectively, interleaved data symbols being derived from the matrix column by column.
Preferably fc(l)=ml where m is an integer; for example m is 1 or is approximately equal to Nr/Nc. If fr(k) is not zero, then preferably fr(k)=nk where n is an integer; for example n=1. Conveniently xcex1r is the largest prime number less than Nr/2, and xcex1c is the largest prime number less than Nc/2.
The actual number of data symbols to be interleaved need not be exactly equal to NrNc but can be a little less than this, in which case preferably the method further comprises the step of determining one or more matrix positions in which data symbols to be interleaved are not represented, interleaved data symbols not being derived from such determined matrix positions.
The invention also provides a data symbol interleaver arranged for carrying out a method as recited above.
Another aspect of the invention provides a data interleaver comprising: a memory arranged to sequentially store up to NcNr data symbols to be interleaved at respective addresses, where Nc and Nr are integers greater than 1; a counter arranged to provide an index 1 from 1 to Nc, and a counter arranged to provide an index from 1 to Nr for each value of the index 1; a circuit arranged to determine a first value [(xcex1cl+nk]modNc and a second value [xcex1rk+ml]modNr, where xcex1c, xcex1r, and m are positive integers and n is a positive integer or zero, and modnr and modNc represent modulo-Nr and modulo-Nc arithmetic respectively; and an address combiner arranged to combine the first value as a more significant part and the second value as a less significant part of a read address for reading interleaved data symbols from the memory.
The data interleaver can further comprise an address decoder responsive to at least one read address produced by the address combiner at which a data symbol to be interleaved is not stored in the memory for inhibiting reading from the memory from such address. In this case conveniently the data interleaver further includes a first-in, first-out buffer arranged to buffer interleaved data symbols read from the memory.
The invention further provides a channel interleaver for a communications system including a data rate matching circuit which performs puncturing of data symbols, comprising a data interleaver as recited above.